# sage.doctest: needs sage.libs.pari sage.rings.number_field
r"""
Smooth characters of `p`-adic fields

Let `F` be a finite extension of `\QQ_p`. Then we may consider the group of
smooth (i.e. locally constant) group homomorphisms `F^\times \to L^\times`, for
`L` any field. Such characters are important since they can be used to
parametrise smooth representations of `\mathrm{GL}_2(\QQ_p)`, which arise as
the local components of modular forms.

This module contains classes to represent such characters when `F` is `\QQ_p`
or a quadratic extension. In the latter case, we choose a quadratic extension
`K` of `\QQ` whose completion at `p` is `F`, and use Sage's wrappers of the
Pari :pari:`idealstar` and :pari:`ideallog` methods to work in the finite group
`\mathcal{O}_K / p^c` for `c \ge 0`.

An example with characters of `\QQ_7`::

    sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
    sage: K.<z> = CyclotomicField(42)
    sage: G = SmoothCharacterGroupQp(7, K)
    sage: G.unit_gens(2), G.exponents(2)
    ([3, 7], [42, 0])

The output of the last line means that the group `\QQ_7^\times / (1 + 7^2
\ZZ_7)` is isomorphic to `C_{42} \times \ZZ`, with the two factors being
generated by `3` and `7` respectively. We create a character by specifying the
images of these generators::

    sage: chi = G.character(2, [z^5, 11 + z]); chi
    Character of Q_7*, of level 2, mapping 3 |--> z^5, 7 |--> z + 11
    sage: chi(4)
    z^8
    sage: chi(42)
    z^10 + 11*z^9

Characters are themselves group elements, and basic arithmetic on them works::

    sage: chi**3
    Character of Q_7*, of level 2, mapping 3 |--> z^8 - z, 7 |--> z^3 + 33*z^2 + 363*z + 1331
    sage: chi.multiplicative_order()
    +Infinity
"""

import operator

from sage.arith.functions import lcm
from sage.arith.misc import crt
from sage.categories.groups import Groups
from sage.categories.rings import Rings
from sage.misc.abstract_method import abstract_method
from sage.misc.cachefunc import cached_method
from sage.misc.lazy_import import lazy_import
from sage.misc.misc_c import prod
from sage.misc.mrange import xmrange
from sage.misc.verbose import verbose
from sage.modular.dirichlet import DirichletGroup
from sage.rings.finite_rings.integer_mod_ring import Zmod
from sage.rings.infinity import Infinity
from sage.rings.integer_ring import ZZ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
from sage.rings.rational_field import QQ
from sage.structure.element import MultiplicativeGroupElement, parent
from sage.structure.parent import Parent
from sage.structure.richcmp import richcmp_not_equal, richcmp
from sage.structure.sequence import Sequence

lazy_import('sage.rings.finite_rings.conway_polynomials', 'conway_polynomial')
lazy_import('sage.rings.number_field.number_field', 'NumberField')


class SmoothCharacterGeneric(MultiplicativeGroupElement):
    r"""
    A smooth (i.e. locally constant) character of `F^\times`, for `F` some
    finite extension of `\QQ_p`.
    """
    def __init__(self, parent, c, values_on_gens):
        r"""
        Standard init function.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(2, QQ)
            sage: G.character(0, [17]) # indirect doctest
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 0, mapping 2 |--> 17
            sage: G.character(1, [1, 17]) # indirect doctest
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 0, mapping 2 |--> 17
            sage: G.character(2, [1, -1, 1, 17]) # indirect doctest
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 2, mapping s |--> 1, 2*s + 1 |--> -1, -1 |--> 1, 2 |--> 17
            sage: G.character(2, [1, 1, 1, 17]) # indirect doctest
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 0, mapping 2 |--> 17
        """
        MultiplicativeGroupElement.__init__(self, parent)
        self._c = c
        self._values_on_gens = Sequence(values_on_gens, universe=self.base_ring(), immutable=True)
        self._check_level()

    def _check_level(self):
        r"""
        Checks that this character has the level it claims to have, and if not,
        decrement the level appropriately. This is called by :meth:`__init__`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(5, QQ).character(5, [-1, 7]) # indirect doctest
            Character of Q_5*, of level 1, mapping 2 |--> -1, 5 |--> 7
        """
        if self.level() == 0:
            return
        v = self.parent().subgroup_gens(self.level())
        if all(self(x) == 1 for x in v):
            new_gens = self.parent().unit_gens(self.level() - 1)
            new_values = [self(x) for x in new_gens]
            self._values_on_gens = Sequence(new_values, universe=self.base_ring(), immutable=True)
            self._c = self._c - 1
            self._check_level()

    def __hash__(self):
        r"""
        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: chi = SmoothCharacterGroupQp(5, QQ).character(5, [-1, 7])
            sage: D = {chi: 7}; D[chi] # indirect doctest
            7
        """
        return hash( (self._c, self._values_on_gens) )

    def _richcmp_(self, other, op):
        r"""
        Compare ``self`` and ``other``.

        Note that this only gets called when the
        parents of ``self`` and ``other`` are identical.

        INPUT:

        - ``other`` -- another smooth character

        - ``op`` -- a comparison operator (see :mod:`sage.structure.richcmp`)

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp, SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupQp(7, Zmod(3)).character(1, [2, 1]) == SmoothCharacterGroupQp(7, ZZ).character(1, [-1, 1])
            True
            sage: chi1 = SmoothCharacterGroupUnramifiedQuadratic(7, QQ).character(0, [1])
            sage: chi2 = SmoothCharacterGroupQp(7, QQ).character(0, [1])
            sage: chi1 == chi2
            False
            sage: chi2.parent()(chi1) == chi2
            True
            sage: chi1 == loads(dumps(chi1))
            True
        """
        lx = self.level()
        rx = other.level()
        if lx != rx:
            return richcmp_not_equal(lx, rx, op)

        return richcmp(self._values_on_gens, other._values_on_gens, op)

    def multiplicative_order(self):
        r"""
        Return the order of this character as an element of the character group.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<z> = CyclotomicField(42)
            sage: G = SmoothCharacterGroupQp(7, K)
            sage: G.character(3, [z^10 - z^3, 11]).multiplicative_order()
            +Infinity
            sage: G.character(3, [z^10 - z^3, 1]).multiplicative_order()
            42
            sage: G.character(1, [z^7, z^14]).multiplicative_order()
            6
            sage: G.character(0, [1]).multiplicative_order()
            1
        """
        if self._values_on_gens[-1].multiplicative_order() == Infinity:
            return Infinity
        else:
            return lcm([x.multiplicative_order() for x in self._values_on_gens])

    def level(self):
        r"""
        Return the level of this character, i.e. the smallest integer `c \ge 0`
        such that it is trivial on `1 + \mathfrak{p}^c`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, QQ).character(2, [-1, 1]).level()
            1
        """
        return self._c

    def __call__(self, x):
        r"""
        Evaluate the character at ``x``, which should be a nonzero element of
        the number field of the parent group.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<z> = CyclotomicField(42)
            sage: chi = SmoothCharacterGroupQp(7, K).character(3, [z^10 - z^3, 11])
            sage: [chi(x) for x in [1, 2, 3, 9, 21, 1/12345678]]
            [1, -z, z^10 - z^3, -z^11 - z^10 + z^8 + z^7 - z^6 - z^5 + z^3 + z^2 - 1, 11*z^10 - 11*z^3, z^7 - 1]

        Non-examples::

            sage: chi(QuadraticField(-1,'i').gen())
            Traceback (most recent call last):
            ...
            TypeError: no canonical coercion from Number Field in i with defining polynomial x^2 + 1 with i = 1*I to Rational Field
            sage: chi(0)
            Traceback (most recent call last):
            ...
            ValueError: cannot evaluate at zero
            sage: chi(Mod(1, 12))
            Traceback (most recent call last):
            ...
            TypeError: no canonical coercion from Ring of integers modulo 12 to Rational Field

        Some examples with an unramified quadratic extension, where the choice
        of generators is arbitrary (but deterministic)::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: K.<z> = CyclotomicField(30)
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(5, K)
            sage: chi = G.character(2, [z**5, z**(-6), z**6, 3]); chi
            Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 2, mapping 11*s - 10 |--> z^5, 6 |--> -z^7 - z^6 + z^3 + z^2 - 1, 5*s + 1 |--> z^6, 5 |--> 3
            sage: chi(G.unit_gens(2)[0]**7 / G.unit_gens(2)[1]/5)
            1/3*z^6 - 1/3*z
            sage: chi(2)
            -z^3
        """
        v = self.parent().discrete_log(self.level(), x)
        return prod([self._values_on_gens[i] ** v[i] for i in range(len(v))])

    def _repr_(self):
        r"""
        String representation of this character.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<z> = CyclotomicField(20)
            sage: SmoothCharacterGroupQp(5, K).character(2, [z, z+1])._repr_()
            'Character of Q_5*, of level 2, mapping 2 |--> z, 5 |--> z + 1'

        Examples over field extensions::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: K.<z> = CyclotomicField(15)
            sage: SmoothCharacterGroupUnramifiedQuadratic(5, K).character(2, [z**5, z**3, 1, z+1])._repr_()
            'Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 2, mapping 11*s - 10 |--> z^5, 6 |--> z^3, 5*s + 1 |--> 1, 5 |--> z + 1'
        """
        gens = self.parent().unit_gens(self.level())
        mapst = ", ".join( str(gens[i]) + ' |--> ' + str(self._values_on_gens[i]) for i in range(len(gens)) )
        return "Character of %s, of level %s, mapping %s" % (self.parent()._field_name(), self.level(), mapst)

    def _mul_(self, other):
        r"""
        Product of self and other.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<z> = CyclotomicField(20)
            sage: chi1 = SmoothCharacterGroupQp(5, K).character(2, [z, z+1])
            sage: chi2 = SmoothCharacterGroupQp(5, K).character(2, [z^4, 3])
            sage: chi1 * chi2 # indirect doctest
            Character of Q_5*, of level 1, mapping 2 |--> z^5, 5 |--> 3*z + 3
            sage: chi2 * chi1 # indirect doctest
            Character of Q_5*, of level 1, mapping 2 |--> z^5, 5 |--> 3*z + 3
            sage: chi1 *  SmoothCharacterGroupQp(5, QQ).character(2, [-1, 7]) # indirect doctest
            Character of Q_5*, of level 2, mapping 2 |--> -z, 5 |--> 7*z + 7
        """
        if other.level() > self.level():
            return other * self
        return self.parent().character(self.level(), [self(x) * other(x) for x in self.parent().unit_gens(self.level())])

    def __invert__(self):
        r"""
        Multiplicative inverse of self.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: K.<z> = CyclotomicField(12)
            sage: chi = SmoothCharacterGroupUnramifiedQuadratic(2, K).character(4, [z**4, z**3, z**9, -1, 7]); chi
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 4, mapping s |--> z^2 - 1, 2*s + 1 |--> z^3, 4*s + 1 |--> -z^3, -1 |--> -1, 2 |--> 7
            sage: chi**(-1) # indirect doctest
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 4, mapping s |--> -z^2, 2*s + 1 |--> -z^3, 4*s + 1 |--> z^3, -1 |--> -1, 2 |--> 1/7
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).character(0, [7]) / chi # indirect doctest
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 4, mapping s |--> -z^2, 2*s + 1 |--> -z^3, 4*s + 1 |--> z^3, -1 |--> -1, 2 |--> 1
        """
        return self.parent().character(self.level(), [~self(x) for x in self.parent().unit_gens(self.level())])

    def restrict_to_Qp(self):
        r"""
        Return the restriction of this character to `\QQ_p^\times`, embedded as
        a subfield of `F^\times`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: SmoothCharacterGroupRamifiedQuadratic(3, 0, QQ).character(0, [2]).restrict_to_Qp()
            Character of Q_3*, of level 0, mapping 3 |--> 4
        """
        G = SmoothCharacterGroupQp(self.parent().prime(), self.base_ring())
        ugs = G.unit_gens(self.level())
        return G.character(self.level(), [self(x) for x in ugs])

    def galois_conjugate(self):
        r"""
        Return the composite of this character with the order `2` automorphism of
        `K / \QQ_p` (assuming `K` is quadratic).

        Note that this is the Galois operation on the *domain*, not on the
        *codomain*.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: K.<w> = CyclotomicField(3)
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(2, K)
            sage: chi = G.character(2, [w, -1,-1, 3*w])
            sage: chi2 = chi.galois_conjugate(); chi2
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 2, mapping s |--> -w - 1, 2*s + 1 |--> 1, -1 |--> -1, 2 |--> 3*w

            sage: chi.restrict_to_Qp() == chi2.restrict_to_Qp()
            True
            sage: chi * chi2 == chi.parent().compose_with_norm(chi.restrict_to_Qp())
            True
        """
        K, s = self.parent().number_field().objgen()
        if K.absolute_degree() != 2:
            raise ValueError("Character must be defined on a quadratic extension")
        sigs = K.embeddings(K)
        sig = [x for x in sigs if x(s) != s][0]
        return self.parent().character(self.level(), [self(sig(x)) for x in self.parent().unit_gens(self.level())])


class SmoothCharacterGroupGeneric(Parent):
    r"""
    The group of smooth (i.e. locally constant) characters of a `p`-adic field,
    with values in some ring `R`. This is an abstract base class and should not
    be instantiated directly.
    """

    Element = SmoothCharacterGeneric

    def __init__(self, p, base_ring):
        r"""
        TESTS::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: G = SmoothCharacterGroupGeneric(3, QQ)
            sage: SmoothCharacterGroupGeneric(3, "hello")
            Traceback (most recent call last):
            ...
            TypeError: base ring (=hello) must be a ring
        """
        if base_ring not in Rings():
            raise TypeError("base ring (=%s) must be a ring" % base_ring)
        Parent.__init__(self, base=base_ring,
                        category=Groups().Commutative())
        if not (p in ZZ and ZZ(p).is_prime()):
            raise ValueError("p (=%s) must be a prime integer" % p)
        self._p = ZZ.coerce(p)

    def _element_constructor_(self, x):
        r"""
        Construct an element of this group from ``x`` (possibly noncanonically).
        This only works if ``x`` is a character of a field containing the field of
        self, whose values lie in a field that can be converted into self.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<i> = QuadraticField(-1)
            sage: G = SmoothCharacterGroupQp(3, QQ)
            sage: GK = SmoothCharacterGroupQp(3, K)
            sage: chi = GK(G.character(0, [4])); chi # indirect doctest
            Character of Q_3*, of level 0, mapping 3 |--> 4
            sage: chi.parent() is GK
            True
            sage: G(GK.character(0, [7])) # indirect doctest
            Character of Q_3*, of level 0, mapping 3 |--> 7
            sage: G(GK.character(0, [i])) # indirect doctest
            Traceback (most recent call last):
            ...
            TypeError: unable to convert i to an element of Rational Field
        """
        if x == 1:
            return self.character(0, [1])
        P = parent(x)
        if (isinstance(P, SmoothCharacterGroupGeneric)
                and P.number_field().has_coerce_map_from(self.number_field())):
            return self.character(x.level(), [x(v) for v in self.unit_gens(x.level())])
        else:
            raise TypeError

    def __eq__(self, other):
        r"""
        TESTS::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: G = SmoothCharacterGroupQp(3, QQ)
            sage: G == SmoothCharacterGroupQp(3, QQ[I])
            False
            sage: G == 7
            False
            sage: G == SmoothCharacterGroupQp(7, QQ)
            False
            sage: G == SmoothCharacterGroupQp(3, QQ)
            True
        """
        if not isinstance(other, SmoothCharacterGroupGeneric):
            return False

        return (self.prime() == other.prime() and
                self.number_field() == other.number_field() and
                self.base_ring() == other.base_ring())

    def __ne__(self, other):
        """
        Check whether ``self`` is not equal to ``other``.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: G = SmoothCharacterGroupQp(3, QQ)
            sage: G != SmoothCharacterGroupQp(3, QQ[I])
            True
            sage: G != 7
            True
            sage: G != SmoothCharacterGroupQp(7, QQ)
            True
            sage: G != SmoothCharacterGroupQp(3, QQ)
            False
        """
        return not (self == other)

    def __hash__(self):
        """
        Return the hash of ``self``.

        TESTS::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: G = SmoothCharacterGroupQp(3, QQ)
            sage: hash(G) == hash(SmoothCharacterGroupQp(3, QQ[I]))
            False
            sage: hash(G) == hash(SmoothCharacterGroupQp(7, QQ))
            False
            sage: hash(G) == hash(SmoothCharacterGroupQp(3, QQ))
            True
        """
        return hash((self.prime(), self.number_field(), self.base_ring()))

    def _coerce_map_from_(self, other):
        r"""
        Return ``True`` if ``self`` has a canonical coerce map from ``other``.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<i> = QuadraticField(-1)
            sage: G = SmoothCharacterGroupQp(3, QQ)
            sage: GK = SmoothCharacterGroupQp(3, K)
            sage: G.has_coerce_map_from(GK)
            False
            sage: GK.has_coerce_map_from(G)
            True
            sage: GK.coerce(G.character(0, [4]))
            Character of Q_3*, of level 0, mapping 3 |--> 4
            sage: G.coerce(GK.character(0, [4]))
            Traceback (most recent call last):
            ...
            TypeError: no canonical coercion from Group of smooth characters of Q_3* with values in Number Field in i with defining polynomial x^2 + 1 with i = 1*I to Group of smooth characters of Q_3* with values in Rational Field
            sage: G.character(0, [4]) in GK # indirect doctest
            True

        The coercion framework handles base extension, so we test that too::

            sage: K.<i> = QuadraticField(-1)
            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(3, QQ)
            sage: G.character(0, [1]).base_extend(K)
            Character of unramified extension Q_3(s)* (s^2 + 2*s + 2 = 0), of level 0, mapping 3 |--> 1

        """
        return (isinstance(other, SmoothCharacterGroupGeneric)
                and other.number_field() == self.number_field()
                and self.base_ring().has_coerce_map_from(other.base_ring()))

    def prime(self):
        r"""
        The residue characteristic of the underlying field.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ).prime()
            3
        """
        return self._p

    @abstract_method
    def change_ring(self, ring):
        r"""
        Return the character group of the same field, but with values in a
        different coefficient ring. To be implemented by all derived classes
        (since the generic base class can't know the parameters).

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ).change_ring(ZZ)
            Traceback (most recent call last):
            ...
            NotImplementedError: <abstract method change_ring at ...>
        """
        pass

    def base_extend(self, ring):
        r"""
        Return the character group of the same field, but with values in a new
        coefficient ring into which the old coefficient ring coerces. An error
        will be raised if there is no coercion map from the old coefficient
        ring to the new one.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: G = SmoothCharacterGroupQp(3, QQ)
            sage: G.base_extend(QQbar)
            Group of smooth characters of Q_3* with values in Algebraic Field
            sage: G.base_extend(Zmod(3))
            Traceback (most recent call last):
            ...
            TypeError: no canonical coercion from Rational Field to Ring of integers modulo 3

        """
        if not ring.has_coerce_map_from(self.base_ring()):
            ring.coerce(self.base_ring().an_element())
            # this is here to flush out errors

        return self.change_ring(ring)

    @abstract_method
    def _field_name(self):
        r"""
        A string representing the name of the p-adic field of which this is the
        character group. To be overridden by derived subclasses.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ)._field_name()
            Traceback (most recent call last):
            ...
            NotImplementedError: <abstract method _field_name at ...>
        """
        pass

    def _repr_(self):
        r"""
        String representation of self.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, QQ)._repr_()
            'Group of smooth characters of Q_7* with values in Rational Field'
        """
        return "Group of smooth characters of %s with values in %s" % (self._field_name(), self.base_ring())

    @abstract_method
    def ideal(self, level):
        r"""
        Return the ``level``-th power of the maximal ideal of the ring of
        integers of the p-adic field. Since we approximate by using number
        field arithmetic, what is actually returned is an ideal in a number
        field.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ).ideal(3)
            Traceback (most recent call last):
            ...
            NotImplementedError: <abstract method ideal at ...>
        """
        pass

    @abstract_method
    def unit_gens(self, level):
        r"""
        A list of generators `x_1, \dots, x_d` of the abelian group `F^\times /
        (1 + \mathfrak{p}^c)^\times`, where `c` is the given level, satisfying
        no relations other than `x_i^{n_i} = 1` for each `i` (where the
        integers `n_i` are returned by :meth:`exponents`). We adopt the
        convention that the final generator `x_d` is a uniformiser (and `n_d =
        0`).

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ).unit_gens(3)
            Traceback (most recent call last):
            ...
            NotImplementedError: <abstract method unit_gens at ...>
        """
        pass

    @abstract_method
    def exponents(self, level):
        r"""
        The orders `n_1, \dots, n_d` of the generators `x_i` of `F^\times / (1
        + \mathfrak{p}^c)^\times` returned by :meth:`unit_gens`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ).exponents(3)
            Traceback (most recent call last):
            ...
            NotImplementedError: <abstract method exponents at ...>
        """
        pass

    @abstract_method
    def subgroup_gens(self, level):
        r"""
        A set of elements of `(\mathcal{O}_F / \mathfrak{p}^c)^\times`
        generating the kernel of the reduction map to `(\mathcal{O}_F /
        \mathfrak{p}^{c-1})^\times`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ).subgroup_gens(3)
            Traceback (most recent call last):
            ...
            NotImplementedError: <abstract method subgroup_gens at ...>
        """
        pass

    @abstract_method
    def discrete_log(self, level):
        r"""
        Given an element `x \in F^\times` (lying in the number field `K` of
        which `F` is a completion, see module docstring), express the class of
        `x` in terms of the generators of `F^\times / (1 +
        \mathfrak{p}^c)^\times` returned by :meth:`unit_gens`.

        This should be overridden by all derived classes. The method should
        first attempt to canonically coerce `x` into ``self.number_field()``,
        and check that the result is not zero.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ).discrete_log(3)
            Traceback (most recent call last):
            ...
            NotImplementedError: <abstract method discrete_log at ...>
        """
        pass

    def character(self, level, values_on_gens):
        r"""
        Return the unique character of the given level whose values on the
        generators returned by ``self.unit_gens(level)`` are
        ``values_on_gens``.

        INPUT:

        - ``level`` (integer) an integer `\ge 0`
        - ``values_on_gens`` (sequence) a sequence of elements of length equal
          to the length of ``self.unit_gens(level)``. The values should be
          convertible (that is, possibly noncanonically) into the base ring of self; they
          should all be units, and all but the last must be roots of unity (of
          the orders given by ``self.exponents(level)``.

        .. note::

            The character returned may have level less than ``level`` in general.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<z> = CyclotomicField(42)
            sage: G = SmoothCharacterGroupQp(7, K)
            sage: G.character(2, [z^6, 8])
            Character of Q_7*, of level 2, mapping 3 |--> z^6, 7 |--> 8
            sage: G.character(2, [z^7, 8])
            Character of Q_7*, of level 1, mapping 3 |--> z^7, 7 |--> 8

        Non-examples::

            sage: G.character(1, [z, 1])
            Traceback (most recent call last):
            ...
            ValueError: value on generator 3 (=z) should be a root of unity of order 6
            sage: G.character(1, [1, 0])
            Traceback (most recent call last):
            ...
            ValueError: value on uniformiser 7 (=0) should be a unit

        An example with a funky coefficient ring::

            sage: G = SmoothCharacterGroupQp(7, Zmod(9))
            sage: G.character(1, [2, 2])
            Character of Q_7*, of level 1, mapping 3 |--> 2, 7 |--> 2
            sage: G.character(1, [2, 3])
            Traceback (most recent call last):
            ...
            ValueError: value on uniformiser 7 (=3) should be a unit

        TESTS::

            sage: G.character(1, [2])
            Traceback (most recent call last):
            ...
            AssertionError: 2 images must be given
        """
        S = Sequence(values_on_gens, universe=self.base_ring(), immutable=True)
        assert len(S) == len(self.unit_gens(level)), "{0} images must be given".format(len(self.unit_gens(level)))
        n = self.exponents(level)
        for i in range(len(S)):
            if n[i] != 0 and not S[i]**n[i] == 1:
                raise ValueError( "value on generator %s (=%s) should be a root of unity of order %s" % (self.unit_gens(level)[i], S[i], n[i]) )
            elif n[i] == 0 and not S[i].is_unit():
                raise ValueError( "value on uniformiser %s (=%s) should be a unit" % (self.unit_gens(level)[i], S[i]) )
        return self.element_class(self, level, S)

    def norm_character(self):
        r"""
        Return the normalised absolute value character in this group (mapping a
        uniformiser to `1/q` where `q` is the order of the residue field).

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp, SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupQp(5, QQ).norm_character()
            Character of Q_5*, of level 0, mapping 5 |--> 1/5
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).norm_character()
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 0, mapping 2 |--> 1/4
        """
        return self.character(0, [1/self.ideal(1).residue_field().cardinality()])

    def _an_element_(self):
        r"""
        Return an element of this group. Required by the coercion machinery.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<z> = CyclotomicField(42)
            sage: G = SmoothCharacterGroupQp(7, K)
            sage: G.an_element() # indirect doctest
            Character of Q_7*, of level 0, mapping 7 |--> z
        """
        return self.character(0, [self.base_ring().an_element()])

    def _test_unitgens(self, **options):
        r"""
        Test that the generators returned by ``unit_gens`` are consistent with
        the exponents returned by ``exponents``.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, Zmod(8))._test_unitgens()
        """
        T = self._tester(**options)
        for c in range(6):
            gens = self.unit_gens(c)
            exps = self.exponents(c)
            T.assertEqual(exps[-1], 0)
            T.assertTrue(all(u != 0 for u in exps[:-1]))
            T.assertTrue(all(u.parent() is self.number_field() for u in gens))

            I = self.ideal(c)
            for i in range(len(exps[:-1])):
                g = gens[i]
                for m in range(1, exps[i]):
                    if (g - 1 in I):
                        T.fail("For generator g=%s, g^%s = %s = 1 mod I, but order should be %s" % (gens[i], m, g, exps[i]))
                    g = g * gens[i]
                    # reduce g mod I
                    if hasattr(I, "small_residue"):
                        g = I.small_residue(g)
                    else:  # I is an ideal of ZZ
                        g = g % (I.gen())
                if g - 1 not in I:
                    T.fail("For generator g=%s, g^%s = %s, which is not 1 mod I" % (gens[i], exps[i], g))
            I = self.prime() if self.number_field() == QQ else self.ideal(1)
            T.assertEqual(gens[-1].valuation(I), 1)

            # This implicitly tests that the gens really are gens!
            self.discrete_log(c, -1)

    def _test_subgroupgens(self, **options):
        r"""
        Test that the values returned by :meth:`~subgroup_gens` are valid.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(2, CC)._test_subgroupgens()
        """
        T = self._tester(**options)
        for c in range(1, 6):
            sgs = self.subgroup_gens(c)
            I2 = self.ideal(c - 1)
            T.assertTrue(all(x - 1 in I2 for x in sgs), "Kernel gens at level %s not in kernel!" % c)

            # now find the exponent of the kernel

            n1 = prod(self.exponents(c)[:-1])
            n2 = prod(self.exponents(c - 1)[:-1])
            n = n1 // n2
            # if c > 1, n will be a prime here, so that logs below gets calculated correctly

            logs = []
            for idx in xmrange(len(sgs)*[n]):
                y = prod( map(operator.pow, sgs, idx) )
                L = tuple(self.discrete_log(c, y))
                if L not in logs:
                    logs.append(L)
            T.assertEqual(n2 * len(logs), n1, "Kernel gens at level %s don't generate everything!" % c)

    def compose_with_norm(self, chi):
        r"""
        Calculate the character of `K^\times` given by `\chi \circ \mathrm{Norm}_{K/\QQ_p}`.
        Here `K` should be a quadratic extension and `\chi` a character of `\QQ_p^\times`.

        EXAMPLES:

        When `K` is the unramified quadratic extension, the level of the new character is the same as the old::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp, SmoothCharacterGroupRamifiedQuadratic, SmoothCharacterGroupUnramifiedQuadratic
            sage: K.<w> = CyclotomicField(6)
            sage: G = SmoothCharacterGroupQp(3, K)
            sage: chi = G.character(2, [w, 5])
            sage: H = SmoothCharacterGroupUnramifiedQuadratic(3, K)
            sage: H.compose_with_norm(chi)
            Character of unramified extension Q_3(s)* (s^2 + 2*s + 2 = 0), of level 2, mapping -2*s |--> -1, 4 |--> -w, 3*s + 1 |--> w - 1, 3 |--> 25

        In ramified cases, the level of the new character may be larger:

        .. link

        ::

            sage: H = SmoothCharacterGroupRamifiedQuadratic(3, 0, K)
            sage: H.compose_with_norm(chi)
            Character of ramified extension Q_3(s)* (s^2 - 3 = 0), of level 3, mapping 2 |--> w - 1, s + 1 |--> -w, s |--> -5

        On the other hand, since norm is not surjective, the result can even be trivial:

        .. link

        ::

            sage: chi = G.character(1, [-1, -1]); chi
            Character of Q_3*, of level 1, mapping 2 |--> -1, 3 |--> -1
            sage: H.compose_with_norm(chi)
            Character of ramified extension Q_3(s)* (s^2 - 3 = 0), of level 0, mapping s |--> 1
        """
        if chi.parent().number_field() != QQ:
            raise ValueError
        if self.number_field().absolute_degree() != 2:
            raise ValueError
        n = chi.level()
        P = chi.parent().prime() ** n
        m = self.number_field()(P).valuation(self.ideal(1))
        return self.character(m, [chi(x.norm(QQ)) for x in self.unit_gens(m)])


class SmoothCharacterGroupQp(SmoothCharacterGroupGeneric):
    r"""
    The group of smooth characters of `\QQ_p^\times`, with values in some fixed
    base ring.

    EXAMPLES::

        sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
        sage: G = SmoothCharacterGroupQp(7, QQ); G
        Group of smooth characters of Q_7* with values in Rational Field
        sage: TestSuite(G).run()
        sage: G == loads(dumps(G))
        True
    """
    def unit_gens(self, level):
        r"""
        Return a set of generators `x_1, \dots, x_d` for `\QQ_p^\times / (1 +
        p^c \ZZ_p)^\times`. These must be independent in the sense that there
        are no relations between them other than relations of the form
        `x_i^{n_i} = 1`. They need not, however, be in Smith normal form.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, QQ).unit_gens(3)
            [3, 7]
            sage: SmoothCharacterGroupQp(2, QQ).unit_gens(4)
            [15, 5, 2]
        """
        if level == 0:
            return [QQ(self.prime())]
        else:
            return [QQ(x) for x in Zmod(self.prime()**level).unit_gens()] + [QQ(self.prime())]

    def exponents(self, level):
        r"""
        Return the exponents of the generators returned by :meth:`unit_gens`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, QQ).exponents(3)
            [294, 0]
            sage: SmoothCharacterGroupQp(2, QQ).exponents(4)
            [2, 4, 0]
        """
        if level == 0:
            return [0]
        return [x.multiplicative_order() for x in Zmod(self.prime()**level).unit_gens()] + [0]

    def change_ring(self, ring):
        r"""
        Return the group of characters of the same field but with values in a
        different ring. This need not have anything to do with the original
        base ring, and in particular there won't generally be a coercion map
        from self to the new group -- use
        :meth:`~SmoothCharacterGroupGeneric.base_extend` if you want this.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, Zmod(3)).change_ring(CC)
            Group of smooth characters of Q_7* with values in Complex Field with 53 bits of precision
        """
        return SmoothCharacterGroupQp(self.prime(), ring)

    def number_field(self):
        r"""
        Return the number field used for calculations (a dense subfield of the
        local field of which this is the character group). In this case, this
        is always the rational field.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, Zmod(3)).number_field()
            Rational Field
        """
        return QQ

    def ideal(self, level):
        r"""
        Return the ``level``-th power of the maximal ideal. Since we
        approximate by using rational arithmetic, what is actually returned is
        an ideal of `\ZZ`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, Zmod(3)).ideal(2)
            Principal ideal (49) of Integer Ring
        """
        return ZZ.ideal(self.prime() ** level)

    def _field_name(self):
        r"""
        Return a string representation of the field unit group of which this is
        the character group.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, Zmod(3))._field_name()
            'Q_7*'
        """
        return "Q_%s*" % self.prime()

    def discrete_log(self, level, x):
        r"""
        Express the class of `x` in `\QQ_p^\times / (1 + p^c)^\times` in terms
        of the generators returned by :meth:`unit_gens`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: G = SmoothCharacterGroupQp(7, QQ)
            sage: G.discrete_log(0, 14)
            [1]
            sage: G.discrete_log(1, 14)
            [2, 1]
            sage: G.discrete_log(5, 14)
            [9308, 1]
        """
        x = self.number_field().coerce(x)
        if x == 0:
            raise ValueError( "cannot evaluate at zero" )
        s = x.valuation(self.prime())
        return Zmod(self.prime()**level)(x / self.prime()**s).generalised_log() + [s]

    def subgroup_gens(self, level):
        r"""
        Return a list of generators for the kernel of the map `(\ZZ_p / p^c)^\times
        \to (\ZZ_p / p^{c-1})^\times`.

        INPUT:

        - ``c`` (integer) an integer `\ge 1`

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: G = SmoothCharacterGroupQp(7, QQ)
            sage: G.subgroup_gens(1)
            [3]
            sage: G.subgroup_gens(2)
            [8]

            sage: G = SmoothCharacterGroupQp(2, QQ)
            sage: G.subgroup_gens(1)
            []
            sage: G.subgroup_gens(2)
            [3]
            sage: G.subgroup_gens(3)
            [5]
        """
        if level == 0:
            raise ValueError
        elif level == 1:
            return self.unit_gens(level)[:-1]
        else:
            return [1 + self.prime()**(level - 1)]

    def from_dirichlet(self, chi):
        r"""
        Given a Dirichlet character `\chi`, return the factor at p of the
        adelic character `\phi` which satisfies `\phi(\varpi_\ell) =
        \chi(\ell)` for almost all `\ell`, where `\varpi_\ell` is a uniformizer
        at `\ell`.

        More concretely, if we write `\chi = \chi_p \chi_M` as a product of
        characters of p-power, resp prime-to-p, conductor, then this function
        returns the character of `\QQ_p^\times` sending `p` to `\chi_M(p)` and
        agreeing with `\chi_p^{-1}` on integers that are 1 modulo M and coprime
        to `p`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: G = SmoothCharacterGroupQp(3, CyclotomicField(6))
            sage: G.from_dirichlet(DirichletGroup(9).0)
            Character of Q_3*, of level 2, mapping 2 |--> -zeta6 + 1, 3 |--> 1
        """
        p = self.prime()
        chi = chi.primitive_character()
        c = chi.level().valuation(p)
        M = chi.level().prime_to_m_part(p)
        return self.character(chi.conductor().valuation(p), [~chi(crt(1, x, M, p**c)) for x in self.unit_gens(c)[:-1]] + [chi(crt(p, 1, M, p**c))])

    def quadratic_chars(self):
        r"""
        Return a list of the (non-trivial) quadratic characters in this group.
        This will be a list of 3 characters, unless `p = 2` when there are 7.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, QQ).quadratic_chars()
            [Character of Q_7*, of level 0, mapping 7 |--> -1,
             Character of Q_7*, of level 1, mapping 3 |--> -1, 7 |--> -1,
             Character of Q_7*, of level 1, mapping 3 |--> -1, 7 |--> 1]
            sage: SmoothCharacterGroupQp(2, QQ).quadratic_chars()
            [Character of Q_2*, of level 0, mapping 2 |--> -1,
             Character of Q_2*, of level 2, mapping 3 |--> -1, 2 |--> -1,
             Character of Q_2*, of level 2, mapping 3 |--> -1, 2 |--> 1,
             Character of Q_2*, of level 3, mapping 7 |--> -1, 5 |--> -1, 2 |--> -1,
             Character of Q_2*, of level 3, mapping 7 |--> -1, 5 |--> -1, 2 |--> 1,
             Character of Q_2*, of level 3, mapping 7 |--> 1, 5 |--> -1, 2 |--> -1,
             Character of Q_2*, of level 3, mapping 7 |--> 1, 5 |--> -1, 2 |--> 1]
        """
        if self.prime() == 2:
            q = 3
        else:
            q = 1
        ram = [self.from_dirichlet(chi) for chi in DirichletGroup(self.prime() ** q, QQ) if not chi.is_trivial()]
        nr = self.character(0, [-1])
        return sorted([nr] + list(ram) + [f*nr for f in ram])

class SmoothCharacterGroupQuadratic(SmoothCharacterGroupGeneric):
    r"""
    The group of smooth characters of `E^\times`, where `E` is a quadratic extension of `\QQ_p`.
    """

    def discrete_log(self, level, x, gens=None):
        r"""
        Express the class of `x` in `F^\times / (1 + \mathfrak{p}^c)^\times` in
        terms of the generators returned by ``self.unit_gens(level)``, or a
        custom set of generators if given.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(2, QQ)
            sage: G.discrete_log(0, 12)
            [2]
            sage: G.discrete_log(1, 12)
            [0, 2]
            sage: v = G.discrete_log(5, 12); v
            [0, 2, 0, 1, 2]
            sage: g = G.unit_gens(5); prod([g[i]**v[i] for i in [0..4]])/12 - 1 in G.ideal(5)
            True
            sage: G.discrete_log(3,G.number_field()([1,1]))
            [2, 0, 0, 1, 0]
            sage: H = SmoothCharacterGroupUnramifiedQuadratic(5, QQ)
            sage: x = H.number_field()([1,1]); x
            s + 1
            sage: v = H.discrete_log(5, x); v
            [22, 263, 379, 0]
            sage: h = H.unit_gens(5); prod([h[i]**v[i] for i in [0..3]])/x - 1 in H.ideal(5)
            True

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: G = SmoothCharacterGroupRamifiedQuadratic(3, 1, QQ)
            sage: s = G.number_field().gen()
            sage: dl = G.discrete_log(4, 3 + 2*s)
            sage: gs = G.unit_gens(4); gs[0]^dl[0] * gs[1]^dl[1] * gs[2]^dl[2] * gs[3]^dl[3] - (3 + 2*s) in G.ideal(4)
            True

        An example with a custom generating set::

            sage: G.discrete_log(2, s+3, gens=[s, s+1, 2])
            [1, 2, 0]
        """
        x = self.number_field().coerce(x)
        if x == 0:
            raise ValueError( "cannot evaluate at zero" )
        if gens is None:
            n1 = x.valuation(self.ideal(1))
            x1 = x / self.unit_gens(0)[-1] ** n1
            if level == 0:
                return [n1]
            else:
                return self.ideal(level).ideallog(x1, self.unit_gens(level)[:-1]) + [n1]
        else:
            P = self.ideal(1)
            I = self.ideal(level)
            gens = [self.number_field().coerce(g) for g in gens]
            i = min(i for i in range(len(gens)) if gens[i].valuation(P) == 1) # lazy!
            pi = gens[i]
            genvals = []
            genunits = []
            for g in gens:
                genvals.append(g.valuation(P))
                gu = g / pi**genvals[-1]
                gu *= gu.denominator_ideal().element_1_mod(I)
                genunits.append(I.reduce(gu))
            xunit = x / pi**x.valuation(P)
            xunit = I.reduce(xunit * xunit.denominator_ideal().element_1_mod(I))
            verbose("computing log of %s in basis %s" % (xunit, genunits), level=1)
            dl = I.ideallog(xunit, genunits)
            pi_term = x.valuation(P) - sum(dl[j] * genvals[j] for j in range(len(gens)))
            dl[i] += pi_term
            X = prod(gens[j] ** dl[j] for j in range(len(gens)))
            assert (X/x - 1).valuation(P) >= level
            return dl

    @cached_method
    def quotient_gens(self, n):
        r"""
        Return a list of elements of `E` which are a generating set for the
        quotient `E^\times / \QQ_p^\times`, consisting of elements which are
        "minimal" in the sense of [LW12].

        In the examples we implement here, this quotient is almost always
        cyclic: the exceptions are the unramified quadratic extension of
        `\QQ_2` for `n \ge 3`, and the extension `\QQ_3(\sqrt{-3})` for `n \ge
        4`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(7,QQ)
            sage: G.quotient_gens(1)
            [2*s - 2]
            sage: G.quotient_gens(2)
            [15*s + 21]
            sage: G.quotient_gens(3)
            [-75*s + 33]

        A ramified case::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: G = SmoothCharacterGroupRamifiedQuadratic(7, 0, QQ)
            sage: G.quotient_gens(3)
            [22*s + 21]

        An example where the quotient group is not cyclic::

            sage: G = SmoothCharacterGroupUnramifiedQuadratic(2,QQ)
            sage: G.quotient_gens(1)
            [s + 1]
            sage: G.quotient_gens(2)
            [-s + 2]
            sage: G.quotient_gens(3)
            [-17*s - 14, 3*s - 2]
        """

        # silly special case
        if n == 0:
            if self.ideal(1).norm().is_prime():
                return [self.unit_gens(0), [2]]
            else:
                return [[], []]

        p = self.prime()
        I = self.ideal(n)
        gs = self.unit_gens(n)
        es = self.exponents(n)
        d = len(es)

        A = ZZ**d
        R = [A.gen(i)*es[i] for i in range(d)]
        r = I.smallest_integer()
        S = [self.discrete_log(n, ZZ(s)) for s in Zmod(r).unit_gens() + (p,)]
        Q = A / A.span(R + S)
        t = None
        qgs = []
        for v in Q.gens():
            # choose a "nice" representative
            vv = v.lift()
            if vv[-1] < 0:
                vv *= -1
            while vv[-1] not in [0, 1]:
                if t is None:
                    t = self.discrete_log(n, p)
                vv = [vv[i] - t[i] for i in range(d)]
            assert (Q(A(vv)) == v or Q(A(vv)) == -v)
            qgs.append( I.reduce(prod(gs[i] ** (vv[i] % es[i]) for i in range(d-1))) * gs[-1]**vv[-1] )

        if len(qgs) == 2:
            x, y = qgs
            return [x * y, y]
        else:
            return qgs

    def _reduce_Qp(self, level, x):
        r"""
        Utility function: given an element `x` of the number field of self,
        return an element of `\QQ_p^\times` which is congruent to `x` modulo a
        given power of the maximal ideal. An error will be raised if no such
        element exists.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(2, QQ)
            sage: s = G.number_field().gen()
            sage: G._reduce_Qp(3, -2520*s-1007)
            9
            sage: G._reduce_Qp(3, s)
            Traceback (most recent call last):
            ...
            ValueError: s not congruent mod Fractional ideal (8) to an elt of Qp
        """
        p = self.prime()
        r = ZZ(x.norm().valuation(p) / 2)
        y = x / p**r
        if p == 2 and y.trace().valuation(2) < 1:
            raise ValueError("%s not congruent mod %s to an elt of Qp" % (x, self.ideal(level)))
        Y = (y.trace() / 2) % self.ideal(level).smallest_integer()
        X = p**r * Y
        if not (X/x - 1).valuation(self.ideal(1)) >= level:
            if p != 2:
                raise ValueError("%s not congruent mod %s to an elt of Qp" % (x, self.ideal(level)))
            else:
                X += ZZ(2)**(r + level - 1)
                if not (X/x - 1).valuation(self.ideal(1)) >= level:
                    raise ValueError("%s not congruent mod %s to an elt of Qp" % (x, self.ideal(level)))
        return X

    def extend_character(self, level, chi, vals, check=True):
        r"""
        Return the unique character of `F^\times` which coincides with `\chi`
        on `\QQ_p^\times` and maps the generators of the quotient returned by
        :meth:`quotient_gens` to ``vals``.

        INPUT:

        - ``chi``: a smooth character of `\QQ_p`, where `p` is the residue
          characteristic of `F`, with values in the base ring of self (or some
          other ring coercible to it)
        - ``level``: the level of the new character (which should be at least
          the level of ``chi``)
        - ``vals``: a list of elements of the base ring of self (or some other
          ring coercible to it), specifying values on the quotients returned by
          :meth:`quotient_gens`.

        A :class:`ValueError` will be raised if `x^t \ne \chi(\alpha^t)`, where `t`
        is the smallest integer such that `\alpha^t` is congruent modulo
        `p^{\rm level}` to an element of `\QQ_p`.

        EXAMPLES:

        We extend an unramified character of `\QQ_3^\times` to the unramified
        quadratic extension in various ways.

        ::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp, SmoothCharacterGroupUnramifiedQuadratic
            sage: chi = SmoothCharacterGroupQp(5, QQ).character(0, [7]); chi
            Character of Q_5*, of level 0, mapping 5 |--> 7
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(5, QQ)
            sage: G.extend_character(1, chi, [-1])
            Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 1, mapping s |--> -1, 5 |--> 7
            sage: G.extend_character(2, chi, [-1])
            Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 1, mapping s |--> -1, 5 |--> 7
            sage: G.extend_character(3, chi, [1])
            Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 0, mapping 5 |--> 7
            sage: K.<z> = CyclotomicField(6); G.base_extend(K).extend_character(1, chi, [z])
            Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 1, mapping s |--> -z + 1, 5 |--> 7

        We extend the nontrivial quadratic character::

            sage: chi = SmoothCharacterGroupQp(5, QQ).character(1, [-1, 7])
            sage: K.<z> = CyclotomicField(24); G.base_extend(K).extend_character(1, chi, [z^6])
            Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 1, mapping s |--> -z^6, 5 |--> 7

        Extensions of higher level::

            sage: K.<z> = CyclotomicField(20); rho = G.base_extend(K).extend_character(2, chi, [z]); rho
            Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 2, mapping 11*s - 10 |--> z^5, 6 |--> 1, 5*s + 1 |--> z^4, 5 |--> 7
            sage: rho(3)
            -1

        Examples where it doesn't work::

            sage: G.extend_character(1, chi, [1])
            Traceback (most recent call last):
            ...
            ValueError: Invalid values for extension

            sage: G = SmoothCharacterGroupQp(2, QQ); H = SmoothCharacterGroupUnramifiedQuadratic(2, QQ)
            sage: chi = G.character(3, [1, -1, 7])
            sage: H.extend_character(2, chi, [-1])
            Traceback (most recent call last):
            ...
            ValueError: Level of extended character cannot be smaller than level of character of Qp
        """
        chi = chi.base_extend(self.base_ring())

        qs = self.quotient_gens(level)
        assert len(vals) == len(qs)

        # initial sanity checks
        r = self.ideal(level).smallest_integer().valuation(self.prime())
        if chi.level() > r:
            raise ValueError("Level of extended character cannot be smaller than level of character of Qp")

        # now do the calculation
        standard_gens = self.unit_gens(level)
        values_on_standard_gens = []

        custom_gens = qs + chi.parent().unit_gens(r)
        values_on_custom_gens = vals + [chi(x) for x in chi.parent().unit_gens(r)]
        verbose("want to send %s to %s" % (custom_gens, values_on_custom_gens), level=1)

        for x in standard_gens:
            d = self.discrete_log(level, x, custom_gens)
            chix = prod(values_on_custom_gens[i]**d[i] for i in range(len(d)))
            values_on_standard_gens.append(chix)

        chiE = self.character(level, values_on_standard_gens)
        if not all( chiE(qs[i]) == vals[i] for i in range(len(qs)) ) or chiE.restrict_to_Qp() != chi:
            raise ValueError("Invalid values for extension")
        return chiE

class SmoothCharacterGroupUnramifiedQuadratic(SmoothCharacterGroupQuadratic):
    r"""
    The group of smooth characters of `\QQ_{p^2}^\times`, where `\QQ_{p^2}` is
    the unique unramified quadratic extension of `\QQ_p`. We represent
    `\QQ_{p^2}^\times` internally as the completion at the prime above `p` of a
    quadratic number field, defined by (the obvious lift to `\ZZ` of) the
    Conway polynomial modulo `p` of degree 2.

    EXAMPLES::

        sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
        sage: G = SmoothCharacterGroupUnramifiedQuadratic(3, QQ); G
        Group of smooth characters of unramified extension Q_3(s)* (s^2 + 2*s + 2 = 0) with values in Rational Field
        sage: G.unit_gens(3)
        [-11*s, 4, 3*s + 1, 3]
        sage: TestSuite(G).run()
        sage: TestSuite(SmoothCharacterGroupUnramifiedQuadratic(2, QQ)).run()
    """

    def __init__(self, prime, base_ring, names='s'):
        r"""
        Standard initialisation function.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(3, QQ, 'foo'); G
            Group of smooth characters of unramified extension Q_3(foo)* (foo^2 + 2*foo + 2 = 0) with values in Rational Field
            sage: G == loads(dumps(G))
            True
        """
        SmoothCharacterGroupGeneric.__init__(self, prime, base_ring)
        self._name = names

    def change_ring(self, ring):
        r"""
        Return the character group of the same field, but with values in a
        different coefficient ring. This need not have anything to do with the
        original base ring, and in particular there won't generally be a
        coercion map from self to the new group -- use
        :meth:`~SmoothCharacterGroupGeneric.base_extend` if you want this.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, Zmod(3), names='foo').change_ring(CC)
            Group of smooth characters of unramified extension Q_7(foo)* (foo^2 + 6*foo + 3 = 0) with values in Complex Field with 53 bits of precision
        """
        # We want to make sure that both G and the base-extended version have
        # the same values in the cache.
        from copy import copy
        G = SmoothCharacterGroupUnramifiedQuadratic(self.prime(), ring, self._name)
        try:
            G._cache___ideal = copy(self._cache___ideal)
        except AttributeError:
            pass
        return G

    def _field_name(self):
        r"""
        A string representing the unit group of which this is the character group.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, Zmod(3), 'a')._field_name()
            'unramified extension Q_7(a)* (a^2 + 6*a + 3 = 0)'
        """
        return "unramified extension Q_%s(%s)* (%s = 0)" % (self.prime(), self._name, self.number_field().polynomial().change_variable_name(self._name))

    def number_field(self):
        r"""
        Return a number field of which this is the completion at `p`, defined by a polynomial
        whose discriminant is not divisible by `p`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ, 'a').number_field()
            Number Field in a with defining polynomial x^2 + 6*x + 3
            sage: SmoothCharacterGroupUnramifiedQuadratic(5, QQ, 'b').number_field()
            Number Field in b with defining polynomial x^2 + 4*x + 2
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ, 'c').number_field()
            Number Field in c with defining polynomial x^2 + x + 1
        """
        fbar = conway_polynomial(self.prime(), 2)
        f = PolynomialRing(QQ, 'x')([a.lift() for a in fbar])
        return NumberField(f, self._name)

    @cached_method
    def ideal(self, c):
        r"""
        Return the ideal `p^c` of ``self.number_field()``. The result is
        cached, since we use the methods
        :meth:`~sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal.idealstar` and
        :meth:`~sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal.ideallog` which
        cache a Pari ``bid`` structure.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(7, QQ, 'a'); I = G.ideal(3); I
            Fractional ideal (343)
            sage: I is G.ideal(3)
            True
        """
        return self.number_field().ideal(self.prime()**c)

    @cached_method
    def unit_gens(self, c):
        r"""
        A list of generators `x_1, \dots, x_d` of the abelian group `F^\times /
        (1 + \mathfrak{p}^c)^\times`, where `c` is the given level, satisfying
        no relations other than `x_i^{n_i} = 1` for each `i` (where the
        integers `n_i` are returned by :meth:`exponents`). We adopt the
        convention that the final generator `x_d` is a uniformiser (and `n_d =
        0`).

        ALGORITHM: Use Teichmueller lifts.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ).unit_gens(0)
            [7]
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ).unit_gens(1)
            [s, 7]
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ).unit_gens(2)
            [22*s, 8, 7*s + 1, 7]
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ).unit_gens(3)
            [169*s + 49, 8, 7*s + 1, 7]

        In the 2-adic case there can be more than 4 generators::

            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).unit_gens(0)
            [2]
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).unit_gens(1)
            [s, 2]
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).unit_gens(2)
            [s, 2*s + 1, -1, 2]
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).unit_gens(3)
            [s, 2*s + 1, 4*s + 1, -1, 2]
        """
        # special cases

        p = self.prime()
        K = self.number_field()
        a = K.gen()

        if c == 0:
            return [K(p)]
        elif c == 1:
            return [a, K(p)]
        elif p == 2:
            if c == 2:
                return [a, 1 + 2*a, K(-1), K(2)]
            else:
                return [a, 1 + 2*a, 1 + 4*a, K(-1), K(2)]

        # general case

        b = a
        I = self.ideal(c)

        while b**(p**2 - 1) - 1 not in I:
            b = I.reduce(b**(self.prime()**2))
        return [b, K(1 + p), 1 + a*p, K(p)]

    def exponents(self, c):
        r"""
        The orders `n_1, \dots, n_d` of the generators `x_i` of `F^\times / (1
        + \mathfrak{p}^c)^\times` returned by :meth:`unit_gens`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ).exponents(2)
            [48, 7, 7, 0]
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).exponents(3)
            [3, 4, 2, 2, 0]
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).exponents(2)
            [3, 2, 2, 0]
        """
        p = self.prime()
        if c == 0:
            return [0]
        elif c == 1:
            return [p**2 - 1, 0]
        elif p == 2 and c >= 3:
            return [p**2 - 1, p**(c-1), p**(c-2), 2, 0]
        else:
            return [p**2 - 1, p**(c-1), p**(c-1), 0]

    def subgroup_gens(self, level):
        r"""
        A set of elements of `(\mathcal{O}_F / \mathfrak{p}^c)^\times`
        generating the kernel of the reduction map to `(\mathcal{O}_F /
        \mathfrak{p}^{c-1})^\times`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ).subgroup_gens(1)
            [s]
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ).subgroup_gens(2)
            [8, 7*s + 1]
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).subgroup_gens(2)
            [3, 2*s + 1]
        """
        if level == 0:
            raise ValueError
        elif level == 1:
            return self.unit_gens(level)[:-1]
        else:
            return [1 + self.prime()**(level - 1), 1 + self.prime()**(level - 1) * self.number_field().gen()]


class SmoothCharacterGroupRamifiedQuadratic(SmoothCharacterGroupQuadratic):
    r"""
    The group of smooth characters of `K^\times`, where `K` is a ramified
    quadratic extension of `\QQ_p`, and `p \ne 2`.
    """
    def __init__(self, prime, flag, base_ring, names='s'):
        r"""
        Standard initialisation function.

        INPUT:

        - ``prime`` -- a prime integer
        - ``flag`` -- either 0 or 1
        - ``base_ring`` -- a ring
        - ``names`` -- a variable name (default ``s``)

        If ``flag`` is 0, return the group of characters of the multiplicative
        group of the field `\QQ_p(\sqrt{p})`. If ``flag`` is 1, use the
        extension `\QQ_p(\sqrt{dp})`, where `d` is `-1` (if `p = 3 \pmod 4`) or
        the smallest positive quadratic nonresidue mod `p` otherwise.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: G1 = SmoothCharacterGroupRamifiedQuadratic(3, 0, QQ); G1
            Group of smooth characters of ramified extension Q_3(s)* (s^2 - 3 = 0) with values in Rational Field
            sage: G2 = SmoothCharacterGroupRamifiedQuadratic(3, 1, QQ); G2
            Group of smooth characters of ramified extension Q_3(s)* (s^2 - 6 = 0) with values in Rational Field
            sage: G3 = SmoothCharacterGroupRamifiedQuadratic(5, 1, QQ); G3
            Group of smooth characters of ramified extension Q_5(s)* (s^2 - 10 = 0) with values in Rational Field

        TESTS:

        .. link

        ::

            sage: TestSuite(G1).run()
            sage: TestSuite(G2).run()
            sage: TestSuite(G3).run()
        """
        prime = ZZ(prime)
        if prime == 2:
            raise NotImplementedError( "Wildly ramified extensions not supported" )
        SmoothCharacterGroupGeneric.__init__(self, prime, base_ring)
        self._name = names
        if flag not in [0, 1]:
            raise ValueError("Flag must be 0 (for Qp(sqrt(p)) ) or 1 (for the other ramified extension)")
        self._flag = flag

        # Find an integer a such that sqrt(a*p) generates the right field and ZZ(sqrt(a*p)) is integrally closed
        for a in range(4 * prime):
            if (not a % prime) or (not ZZ(a).is_squarefree()) or ((a * prime) % 4 == 1):
                continue
            if (flag == 0 and Zmod(prime)(a).is_square()) or \
                (flag == 1 and not Zmod(prime)(a).is_square()):
                self._unif_sqr = a * prime
                break
        else:
            raise ValueError("Can't get here")

    def change_ring(self, ring):
        r"""
        Return the character group of the same field, but with values in a
        different coefficient ring. This need not have anything to do with the
        original base ring, and in particular there won't generally be a
        coercion map from self to the new group -- use
        :meth:`~SmoothCharacterGroupGeneric.base_extend` if you want this.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: SmoothCharacterGroupRamifiedQuadratic(7, 1, Zmod(3), names='foo').change_ring(CC)
            Group of smooth characters of ramified extension Q_7(foo)* (foo^2 - 35 = 0) with values in Complex Field with 53 bits of precision
        """
        return SmoothCharacterGroupRamifiedQuadratic(self.prime(), self._flag, ring, self._name)

    def _field_name(self):
        r"""
        A string representing the unit group of which this is the character group.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: SmoothCharacterGroupRamifiedQuadratic(7, 0, Zmod(3), 'a')._field_name()
            'ramified extension Q_7(a)* (a^2 - 7 = 0)'
        """
        return "ramified extension Q_%s(%s)* (%s = 0)" % (self.prime(), self._name, self.number_field().polynomial().change_variable_name(self._name))

    def number_field(self):
        r"""
        Return a number field of which this is the completion at `p`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: SmoothCharacterGroupRamifiedQuadratic(7, 0, QQ, 'a').number_field()
            Number Field in a with defining polynomial x^2 - 7
            sage: SmoothCharacterGroupRamifiedQuadratic(5, 1, QQ, 'b').number_field()
            Number Field in b with defining polynomial x^2 - 10
            sage: SmoothCharacterGroupRamifiedQuadratic(7, 1, Zmod(6), 'c').number_field()
            Number Field in c with defining polynomial x^2 - 35
        """
        from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
        R, x = PolynomialRing(QQ, 'x').objgen()
        f = x**2 - self._unif_sqr
        return NumberField(f, self._name)

    @cached_method
    def ideal(self, c):
        r"""
        Return the ideal `p^c` of ``self.number_field()``. The result is
        cached, since we use the methods
        :meth:`~sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal.idealstar` and
        :meth:`~sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal.ideallog` which
        cache a Pari ``bid`` structure.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: G = SmoothCharacterGroupRamifiedQuadratic(5, 1, QQ, 'a'); I = G.ideal(3); I
            Fractional ideal (25, 5*a)
            sage: I is G.ideal(3)
            True
        """
        return self.number_field().ideal([self.prime(), self.number_field().gen()])**c

    def unit_gens(self, c):
        r"""
        A list of generators `x_1, \dots, x_d` of the abelian group `F^\times /
        (1 + \mathfrak{p}^c)^\times`, where `c` is the given level, satisfying
        no relations other than `x_i^{n_i} = 1` for each `i` (where the
        integers `n_i` are returned by :meth:`exponents`). We adopt the
        convention that the final generator `x_d` is a uniformiser.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: G = SmoothCharacterGroupRamifiedQuadratic(5, 0, QQ)
            sage: G.unit_gens(0)
            [s]
            sage: G.unit_gens(1)
            [2, s]
            sage: G.unit_gens(8)
            [2, s + 1, s]
        """
        d = ZZ(c + 1) // 2
        p = self.prime()
        K, s = self.number_field().objgen()
        zpgens = [K(ZZ(x)) for x in Zmod(p**d).unit_gens()]
        if c == 0:
            return [s]
        if c == 1:
            return zpgens + [s]
        elif p > 3 or self._unif_sqr == 3 or c <= 3:
            return zpgens + [1 + s, s]
        else:
            # Awkward case: K = Q_3(sqrt(-3)). Here the exponential map doesn't
            # converge on 1 + P, and the quotient (O_K*) / (Zp*) isn't
            # topologically cyclic. I don't know an explicit set of good
            # generators here, so we let Pari do the work and put up with the
            # rather arbitrary (nondeterministic?) results.
            return list(self.ideal(c).idealstar(2).gens_values()) + [s]

    def exponents(self, c):
        r"""
        Return the orders of the independent generators of the unit group
        returned by :meth:`~unit_gens`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: G = SmoothCharacterGroupRamifiedQuadratic(5, 0, QQ)
            sage: G.exponents(0)
            (0,)
            sage: G.exponents(1)
            (4, 0)
            sage: G.exponents(8)
            (500, 625, 0)
        """
        c = ZZ(c)
        p = self.prime()
        if c == 0:
            return (0,)
        elif c == 1:
            return (p - 1, 0)
        elif p > 3 or self._unif_sqr == 3 or c <= 3:
            d = (c + 1) // 2
            return (p**(d - 1) * (p - 1), p**(c // 2), 0)
        else:
            # awkward case, see above
            return self.ideal(c).idealstar(2).gens_orders() + (0,)

    def subgroup_gens(self, level):
        r"""
        A set of elements of `(\mathcal{O}_F / \mathfrak{p}^c)^\times`
        generating the kernel of the reduction map to `(\mathcal{O}_F /
        \mathfrak{p}^{c-1})^\times`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: G = SmoothCharacterGroupRamifiedQuadratic(3, 1, QQ)
            sage: G.subgroup_gens(2)
            [s + 1]
        """
        if level == 0:
            raise ValueError
        elif level == 1:
            return self.unit_gens(level)[:-1]
        else:
            return [1 + self.number_field().gen()**(level - 1)]
